COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.BEGIN "PREF"
C00015 00003	This text is %6not%* meant to be a programming manual for LISP.
C00030 00004	The text is large and covers much more than is  recommended for a one-semester
C00033 ENDMK
C⊗;
.BEGIN "PREF"
.PREF
.EP;
"... it is important not to lose sight of the fact that there is a difference
between training and education.  If computer science is a fundamental discipline,
then university education in this field should emphasize enduring fundamental
principles rather than transient current technology."
.PT24;
.BEGIN TURN ON"→";
→Peter Wegner, %3Three Computer Cultures%*#[Weg#70]#######
.END
.PT24
.PT24
.PT2
.FP
This text is nominally about LISP and data structures. However, in the process
it 
covers much broader areas of computer science.
The author has long 
felt that the  beginning student of computer science has been getting a distorted 
and disjointed picture of the field. In some ways this confusion is natural; the
field has been growing at such a  rapid rate that few  are prepared
to be judged experts in all areas of the discipline.  The current alternative
seems to be to give a few introductory courses in programming and machine organization
followed by relatively specialized courses in more technical  areas. 
The difficulty with this approach is that much of the technical material
never gets related. The student's perspective and motivation suffers in the
process. This book uses LISP as a means for relating topics which normally
get treated in several  separate  courses. The point is not that we %6can%*
do this in LISP, but rather that it is %6natural%* to do it in LISP.
The high-level notation for algorithms is beneficial in explaining and understanding
complex algorithms.
The use of abstract data structures and abstract LISP programs shows the
 intent of structured programming and step-wise refinement. Much
of the current work in mathematical theories of computation is based on LISP-like
languages. Thus LISP is a formalism for describing algorithms, for writing programs, and
for proving properties of algorithms.
We use data structures as the main thread in our discussions because 
a proper appreciation of data structures as abstract objects is a necessary
prerequisite to an understanding of modern computer science.

The importance of abstraction obviously goes much further than its
appearance in LISP. Abstraction has often been used in other
disciplines as a means for controlling complexity. 
In mathematics, we frequently are able to gain new insights by recasting
a particularly intransigent problem in a more general setting.
Similarly, the intent of an algorithm
expressed in a high-level language like Fortran or PL/1 
is more readily apparent than its machine-language equivalent.
These are both examples of the use of abstraction. Our use of abstraction
will impinge on both the mathematical and the programming aspects.
Initially, we will talk about data structures as abstract objects
just as the mathematician takes  the natural numbers as abstract
entities. We will attempt to categorize properties common to
data structures and introduce notation for describing functions
defined on these abstractions. At this level of discussion
we are thinking of our LISP-like language primarily as a notational
convenience rather than a computational device.
However, after a certain  familiarity
has been established it is important to look at our work from the
viewpoint of computer science. Here we must think of the computational
aspects of our notation. We must be concerned with the representational
problems: implementation on realistic machines, and  efficiency
of algorithms and data structures. However, it cannot be over-emphasized
that our need for understanding is best served at the higher level
of abstraction; the advantage of a high-level language is notational rather
than computational. That is, it allows us to think  and represent our
algorithms in mathematical terms rather than in terms of the machine.
It is only after a clear understanding of the
problem is attained that we should begin thinking about representation.


We can exploit the analogy with traditional mathematics a bit further.
When we write %3sqrt(x)%* in Fortran, for example, we are
initially only concerned with %3sqrt%* as a mathematical function
defined such that %3x#=#sqrt(x)*sqrt(x)%*. We are not interested
in the specific algorithm used to approximate the function
intended in the notation. Indeed, thought of as a mathematical notation,
it doesn't matter how %3sqrt%* is computed. We might wish to prove
some  properties of the algorithm which we are encoding.
If so, we would only use the mathematical properties of the idealized
square root function. Only later, after we had convinced ourselves
of the correct encoding of our intention in the Fortran program,
would we worry about the  computational aspects of the Fortran
implementation %3sqrt%*. The typical user will never
proceed deeper into the representation than this; only if
his computation is lethargic due to inefficiencies, or inaccurate due
to uncooperative approximations, will he look at the actual 
implementation of %3sqrt%*.


Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical or data structure processes.  
We make a  distinction  between data
structures and storage structures. Data structures   are 
abstractions, independent
of %6how%* they are implemented on a machine.  Data structures are representations
of information chosen to exhibit certain ordering and accessibility relationships
between data items.  Storage structures are particular implementations
of the abstract ideas.
Certainly  we cannot ignore
storage structures when we are deciding upon the data structures which
will encode the algorithm, buT the interesting aspects of the representation of
information can be discussed at the level of data structures with no loss
of generality.  The mapping of data structures to storage structures is
usually quite machine dependent 
and 
  we are more interested in ideas than coding tricks.
We will see that it is possible,
and most beneficial, to structure our programs such that there is a very
clean interface between the abstract algorithm and the chosen representation.
That is, there will be a set of representation-manipulating programs to test,
select or construct elements of the domain; and there will be a program
encoding the algorithm. To change representations only requires changes
to constructors, selectors and predicates, not to the basic program.


One important insight which should be cultivated in this process
is the distinction between the concepts of function and algorithm.
The idea of function is mathematical and is independent of any notion
of computation; the meaning of "algorithm" is computational, the
effect of an algorithm being to compute a function. Thus there are
typically many algorithms which will compute a specific function.

This text is %6not%* meant to be a programming manual for LISP.
A certain amount of time is spent giving insights into techniques for
writing LISP functions.  
There are two reasons for this. First, the style
of LISP programming is quite different from that of "normal" programming.
LISP was one of the first languages to exploit the virtues of recursive
programming and explore the power of procedure-valued variables.
Second, we will spend a great deal of time discussing
various levels of implementation of the language. LISP is an excellent
medium for introducing standard techniques 
in data structure manipulation. Techniques for
implementation of recursion, implementation of complex data
structures,  storage management,
and symbol table manipulation are easily motivated in the context
of language implementation. Many of these standard techniques first arose
in the implementation
of LISP. But it is pointless to attempt a discussion
of implementation unless the reader has a thorough grasp of the
language.

Granting the efficacy of our endeavor in abstraction, why study LISP?
LISP is at least fifteen years old and
many languages new languages have been proposed.
The difficulty is that the appropriate combination of these features is not
present in any other language. LISP unifies and rationalizes many divergent
formulations  of language constructs.
One might surmise that a new language, profiting from LISP's experience,
would make a better pedagogical tool.
Toy languages are suspect for several reasons. The student may suspect
  that he is a subject in a not too clever
experiment being performed upon him by his instructor. 
Having a backlog of fifteen years of
experience and example programs should do much to alleviate this discomfort.
The development of LISP also shows many of the mistakes 
that the original implementors and designers made.
We will point out the flaws and pitfalls awaiting the unwary language designer.


We claim
the more interesting aspects of LISP for students of Computer Science lie
not in its features as a programming language, but in what it can show
about the %6structure%* of Computer Science.
There is a
rapidly expanding body of knowledge unique to Computer Science, neither
mathematical nor engineering per se.  Much of this area is presented most
clearly by studying LISP.

Again there are two ways to look at a high level language: as a mathematical
formalism, and as a programming language.
LISP is a better formalism than most of its mathematical rivals
because there is sufficient organizational
complexity present in LISP so as to make its implementation a realistic 
computer science task and not just
an interesting mathematical curiosity.
Much of the power of LISP lies in its simplicity.
The data structures are rich enough  to easily
describe sophisticated algorithms but not so rich as to become obfuscatory.
Most every aspect of the implementation
of LISP and its translators has immediate implications to the implementation of 
other languages and to the design of programming languages in
general.

We will describe language translators (interpreters and compilers) as 
LISP functions.  The structure of these translators when exposed as 
LISP functions aids immensely in understanding the essential
character of such translators.
This is partly due to the simplicity of the language, but perhaps more
due to our ability to go right to the essential translating algorithm 
without becoming
bogged down in details of syntax.

LISP has very important implications in the field of programming language
semantics, and  is the dominant language in the closely related study of
provability of properties of programs.
The idea of proving properties of programs has been around for a very
long time. Goldstine and von Neumann were aware of the practical benefits
of such endeavors. J. McCarthy's work in LISP and the Theory of Computation
sought to establish formalisms and rules of inference for  reasoning
about programs.
However, the  working programmers recognized debugging as the
only tool with which to generate a "correct" program, though  clearly
the non-occurrence of bugs is no guarantee of correctness.
Until
very recently techniques for establishing correctness of practical
programs simply did not exist.

A recent set of events is beginning to change this.
.PT24
.NL
%21.%* Programs are becoming so large and complex that, even though
we write in a high-level language, our intuitions are not sufficient
to sustain us when we try to find bugs. We are literally being forced
to look beyond debugging.
.NL
%22.%* The formalisms are maturing. We know a lot more about how
to write "structured programs"; we know how to design languages
whose constructs are more amenable to proof techniques.
And most importantly, the tools we need for expressing properties of 
programs are finally being developed.
.NL
%23.%* The development of on-line techniques. The on-line system,
with its
sophisticated display editors, debuggers and file handlers,
is the
only reason that the traditional means of construction and
modification of complex programs and systems has been able to survive 
this long.

.PT24

This  view of the programming  process blends well with the LISP philosophy.
We  will show that the most natural way to write LISP programs
is "structured" in the best sense of the word, being  clean in
control structure, concise by not attempting to do too much,
and independent of a particular data representation.

Many of the existing techniques for establishing correctness originated
in McCarthy's investigations of LISP; and some  very recent work
on mathematical models for programming languages is  easily motivated from
a discussion of LISP. 

Finally there are certain properties of LISP-like languages which
make them the natural candidate for  interactive program specification.
In the chapter on implications of LISP we will characterize "LISP-like"
and show how interactive methods can be developed.


This text is primarily designed for undergraduates and therefore
an attempt is made to make it self-contained. 
There are basically five areas in which to partition the topics:
the mechanics of the language, the evaluation of expressions in LISP,
the static structure of LISP, the dynamic structure of LISP, and the
efficient representation of data structures and algorithms.
Each area
builds on the previous. Taken as a group these topics introduce 
much of what is interesting computer science.

The first area develops  the programming philosophy of LISP: the use
of data structures in programming; the language constructs of recursion; and
other uncommon control structures.  The second area involves a careful study of the
meaning of evaluation in LISP gives insights into other languages and to the
general question of implementation. The next two areas are involved with
implementation. The section on static structure deals with the basic 
organization of memory for a LISP machine#--#be it hardware or simulated
in software. The dynamics of LISP  discusses the primitive control structures
necessary for implementation of the LISP control structures  and procedure
calls. LISP compilers are discussed here.
The final section relates our discussion of LISP and its implementation
to the more traditional material of a  data structures course. We discuss the
problems of efficient representation of data structures. By this point
the student should have a better understanding of the uses of data structures
and should be motivated to  examine these issues.

A large collection of problems has been included. The reader is urged to do as
many as possible.  The problems are mostly non-trivial; they attempt to be
realistic, introducing some new information which the readers should be
able to discover themselves. 
There are also a few rather substantial projects.  At least one should be attempted.
There is a significant difference between being able to program small problems
and being able to handle large projects.


The text is large and covers much more than is  recommended for a one-semester
course. 
A typical  one semester course on data structures covers:
.BOXA
.BEGIN INDENT 10,10;NOFILL;
Chapter 1: all
.PT2
Chapter 2: without 2.4 and 2.9.
.PT2
Chapter 3: without 3.12, and mathematical aspects of 3.13
.PT2
Chapter 4: without 4.7, 4.8, and the mathematical aspects of 4.11
.PT2
Chapter 5: without 5.8, 5.19, and 5.20
.PT2
Chapter 6: without 6.8, 6.9, 6.12 through 6.19
.PT2
Chapter 7: without 7.4, 7.5, 7.10 through 7.13
.PT2
Chapter 8 is also optional.
.END
.BOXB

If a  good interactive  LISP implementation is available, then
the pace can be quickened and the projects enlarged.  
However, if only a  poor or mediocre 
implementation is  accessible, then the course time is better spent without
%6any%1  actual programming. LISP is an interactive language; attempts
at other modes of operation do a disservice to both the language and
the user.


Finally a note on the structure of the text. 
The emphasis  flows from the abstract to the specific, beginning
with a precise description of the domain of LISP functions
and the operations defined over that domain, and  moves to a discussion
of the details of efficient implementation of LISP-like languages.
The practical-minded programmer might be put-off by the "irrelevant"
theory and the theoretical-minded mathematician might be put-off
by the "irrelevant" details of implementation. If you lie somewhere  between
these two extremes, then welcome.

.END "PREF"